package hyy_2022;

import java.util.Arrays;

/**
 * 丢失的数字
 * 给定一个包含【0,n】的n个数的数组nums, 找出【0,n】这个范围内没有出现在数组中的那个数
 */
public class _0830_268_MissingNumber {

    /**
     * 方法一: 排序+比较下标
     * 由于数组的长度是n,因此下标范围是[0,n-1]。假设缺失数字是k,分别考虑以下两种情况：
     * 情况1：
            当0 =< k < n,对任意 0 =< i < k,都有nums[i] = i, 由于k的缺失, 因此num[k]=k+1, k是第一个满足下标和元素不相等的下标
       情况2：
            当k=n时,0到n-1都没有缺失,因此对于0 =< i < n,都有nums[i]=i;
     * @param nums
     * @return  int
     */
    public int missingNumberBySort(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for(int i=0;i<n;i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n;
    }
}
